package com.zh.note.leetcode.dp;

import java.util.Arrays;

/**
 * 416. 分割等和子集
 * dp[j] = Math.max(dp[j], dp[j-nums[i]]+nums[i])
 */
public class LC_416_canPartition {

    public boolean canPartition(int[] nums) {

        int sum = Arrays.stream(nums).sum();
        //总和为奇数，不能平分
        if (sum % 2 != 0) return false;
        int target = sum / 2;
        int[] dp = new int[target + 1];
        //初始化,使用默认为0
        for (int i = 0; i < nums.length; i++) { // 遍历物品
            for (int j = target; j >= nums[i]; j--) { // 遍历背包 ，每一个元素一定是不可重复放入，所以从大到小遍历
                //物品 i 的重量是 nums[i]，其价值也是 nums[i]
                dp[j] = Math.max(dp[j], dp[j - nums[i]] + nums[i]);
            }
        }
        return dp[target] == target;
    }
}
